#include <bits/stdc++.h>

using namespace std;


//暴搜。。。用dp优化！！
class Solution1 {
    int count;
public:
    bool can(string s){
        if(s.empty()) return false;
        // cout << s<<endl;
        int len=s.size();
        int x=stoi(s);
        if(len==2&&x<10) return false; //0的特殊情况
        return x>=0&&x<=25;
    }
    void helper(string &str,int index,int len){
        if(index>len) return;
        if(index==len){
            count++;
            return;
        }else{
            for(int i=1;i<=2;i++){
                //cout << str.substr(index,i) <<endl;
                if(can(str.substr(index,i))){
                    
                    helper(str,index+i,len);
                }
            }
        }
    }
    int translateNum(int num) {
        count=0;
        string sn=to_string(num);
        helper(sn,0,sn.size());
        return count;
    }
};

//暴搜。。。用dp优化！！
class Solution3 {
    int count;
public:
    bool can(char a,char b){
        int x=(a-'0')*10+(b-'0');
        return x>=10&& x<=25;
    }
    void helper(string &str,int index,int len){
        if(index>len) return;
        if(index==len){
            count++;
            return;
        }else{
            helper(str,index+1,len);
            
            if(can(str[index],str[index+1])){
                helper(str,index+2,len);
            }
            
        }
    }
    int translateNum(int num) {
        count=0;
        string sn=to_string(num);
        helper(sn,0,sn.size());
        return count;
    }
};

class Solution2 {
public:
    bool can(char a,char b){
        int x=(a-'0')*10+(b-'0');
        return x>=10&& x<=25;
    }
    int translateNum(int num) {
        string sn=to_string(num);
        int len=sn.size();
    
        vector<int> dp(len+5,0);
        dp[0]=dp[1]=1;
        for(int i=2;i<=len;i++){
            if(can(sn[i-2],sn[i-1])){
                dp[i]=dp[i-1]+dp[i-2];
            }else{
                dp[i]=dp[i-1];
            }
        }
        return dp[len];
    }
};
class Solution4 {
public:
    bool can(char a,char b){
        int x=(a-'0')*10+(b-'0');
        return x>=10&& x<=25;
    }
    int translateNum(int num) {
        string sn=to_string(num);
        int len=sn.size();
        int a=1,b=1,c=1;
        for(int i=2;i<=len;i++){
            if(can(sn[i-2],sn[i-1])){
                c=a+b;
            }else{
                c=a;
            }
            b=a;
            a=c;
        }
        return a;
    }
};

class Solution {
public:
    int translateNum(int num) {
        string sn=to_string(num);
        int len=sn.size();
        int a=1,b=1,c=1;
        for(int i=2;i<=len;i++){
            int x=(sn[i-2]-'0')*10+(sn[i-1]-'0');
            c=(x>=10&& x<=25)?a+b:a;
            b=a;
            a=c;
        }
        return a;
    }
};
int main(){
    Solution s;
    cout << s.translateNum(25)<<endl;
    // string ss="25";
    // cout << ss.substr(1,2)<<endl;

    return 0;
}